#include <bits/stdc++.h>

using namespace std;

class ListNode
{
public:
    int val;
    ListNode *next;
    ListNode(int val)
    {
        this->val = val;
        this->next = NULL;
    }
};

ListNode * addLists(ListNode * l1, ListNode * l2)
{
    // write your code here
    if(l1 == NULL)
        return l2;
    if(l2 == NULL)
        return l1;
    ListNode * l3 = new ListNode(0);
    ListNode *l = l3, *l3father;
    while(l1 != NULL || l2 != NULL){
        if(l1 == NULL){
            l3->val += l2->val;
            l2 = l2->next;
        }
        else if(l2 == NULL){
            l3->val += l1->val;
            l1 = l1->next;
        }
        else{
            l3->val = l3->val + l1->val + l2->val;
            l1 = l1->next;
            l2 = l2->next;
        }
        l3->next = new ListNode(0);
        if(l3->val >= 10){
            l3->val %= 10;
            l3->next->val = 1;
        }
        l3father = l3;
        l3 = l3->next;
    }
    if(l3->val == 0)
        l3father->next = NULL;
    return l;
}

void printList(ListNode * l){
    while(l != NULL){
        printf("%d\t", l->val);
        l = l->next;
    }
    printf("\n");
}

int main()
{
    ListNode * l1 = new ListNode(3);
    l1->next = new ListNode(1);
    l1->next->next = new ListNode(5);
    ListNode * l2 = new ListNode(5);
    l2->next = new ListNode(9);
    l2->next->next = new ListNode(2);
    printList(l1);
    printList(l2);
    printList(addLists(l1, l2));
    return 0;
}

/**
 167. 链表求和

你有两个用链表代表的整数，其中每个节点包含一个数字。数字存储按照在原来整数中相反的顺序，使得第一个数字位于链表的开头。写出一个函数将两个整数相加，用链表形式返回和。
您在真实的面试中是否遇到过这个题？
样例

给出两个链表 3->1->5->null 和 5->9->2->null，返回 8->0->8->null
*/
